package com.sx.sx1.lintcode.day717;

import javax.swing.*;
import java.util.HashMap;
import java.util.Map;

public class LC1088 {

    static class Solution {
        /**
         * @param edges: List[List[int]]
         * @return: List[int]
         */
        public int[] findRedundantConnection(int[][] edges) {
            UF uf = new UF();
            for (int[] edge : edges) {
                int a = edge[0];
                int b = edge[1];

                int f1 = uf.find(a);
                int f2 = uf.find(b);

                if(f1 ==f2) return edge;

                uf.union(f1,f2);
            }

            return null;
        }


        static class UF{  //并查集
            public Map<Integer,Integer> parents = new HashMap<>();
            public Map<Integer,Integer> size = new HashMap<>();
            public Map<Integer,Integer> help = new HashMap<>();
            public int sets = 0;

            public int find(int x){
                if(!parents.containsKey(x)){
                    parents.put(x,x);
                    size.put(x,1);
                    sets++;
                }

                int hi=0;
                while (x!=parents.get(x)){
                    help.put(hi++,x);
                    x= parents.get(x);
                }

                for(hi--;hi>=0;hi--){
                    parents.put(help.get(hi),x);
                }

                return x;
            }

            public  void union(int a,int b){
                int f1 = find(a);
                int f2 = find(b);

                if(f1!=f2){
                    int s1 = size.get(f1);
                    int s2= size.get(f2);
                    int sum =s1+s2;
                    if(s1>=s2){
                        size.put(f1,sum);
                        parents.put(f2,f1);
                    }else{
                        size.put(f2,sum);
                        parents.put(f1,f2);
                    }

                    sets--;
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution obj =new Solution();
        int[][] arr1 = {{1,2},{1,3},{2,3}};

        int[][] arr2 = {{1,2},{2,3},{3,4},{1,4},{1,5}};

        int[] data1 = obj.findRedundantConnection(arr1);
        int[] data2 = obj.findRedundantConnection(arr2);
        show(data1);
        show(data2);
    }

    public static void show(int[] arr){
        for (int i : arr) {
            System.out.print(i+" ");
        }
        System.out.println();
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
1088 · 冗余的连接
算法
中等
通过率
66%

题目
题解14
笔记
讨论31
排名
记录
描述
在这个问题中，树是一个连接的、无环的无向图。

给定的输入是一个图形，它以具有N个节点（具有不同的值1,2，...，N）的树开始，并添加了一条额外的边。 添加的边有两个不同的顶点（从1到N中选择），并且不是已经存在的边。

得到的图形以关于边的 2D-数组的形式给出。 边的每个元素是一对[u，v]，其中u <v，这表示连接节点u和v的无向边。

你需要输出可以删除的边，以便生成的图是一棵N个节点的树。 如果有多个答案，则返回给定2D数组中最后出现的答案边。 答案边[u，v]应该采用相同的格式，u <v。

输入2D数组的大小将介于3和1000之间。
2D数组中的每个整数都在1和N之间，其中N是输入数组的大小。

样例
样例 1:

输入:  [[1,2], [1,3], [2,3]]
输出:  [2,3]
解释:
	图如下：
	  1
	 / \
	2 - 3
样例 2:

输入:  [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出:  [1,4]
解释:
	图如下：
	5 - 1 - 2
	    |   |
	    4 - 3
标签
企业
Google
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
23/43
已开启智能提示
发起考试
30 分 00 秒
123456789

控制台
        历史提交

 */
